1. Technical Field
The present invention relates to computer networks, and in particular to apparatus and methods for resolving the problem of non-repudiation of messages transmitted using such networks.
2. Background Information
Confidential or secret data are often transmitted across electronic networks linking separate data processing machines. For example, data relating to banking transactions are often transmitted between bank branches electronically via networks comprising electrical, optical, radio or other communication links, rather than on paper. The need for these networks to provide secure transmission of the data has long been recognized. To this end, sensitive data are commonly enciphered before being transmitted.
The encipherment of data for transmission is described in detail in the book "Security for Computer Networks" (D. W. Davies and W. L. Price, 1984, John Wiley & Sons). There are several methods or algorithms by which data can be enciphered, usually under the control of an encipherment key. However, for the present purposes these algorithms will be considered as two categories, namely symmetric and asymmetric algorithms.
Symmetric algorithms rely on a secret key which is known only to the sender and receiver of a message. The same key is known by both parties, and the system provides a secure bidirectional communications channel between the two parties. An example of a symmetric algorithm is the Data Encryption Standard (DES), which is described in the above reference.
In an asymmetric algorithm (also described in the above reference) the sender and receiver of the message hold different, but complementary, keys. The keys are complementary in that one key can only be used for encipherment, and the other key only for decipherment. Only one of these keys needs to be kept secret, and in fact a major feature of such an algorithm is that the other, non-secret, key can be disclosed widely without compromising security at all. In such a public key system, the data receiver typically holds a secret key, to be used for deciphering received messages. The corresponding encipherment key is made public and is used by any party wishing to send messages to that particular receiver.
A security concern is that it must be possible to establish the authenticity of a message transmitted between two parties. In other words, the recipient should be able to establish that an individual message, purportedly received from a particular sender, was in fact initiated by that sender and has been received without corruption either by network errors or malicious alteration by other parties. This is particularly necessary when there is little redundancy in the message before encipherment; for example a message comprising a long string of digits could appear to be a random sequence under casual inspection. In these cases it would be difficult to tell from the text of the deciphered message alone whether corruption had taken place.
It will also be clear that if the text is enciphered using a public key system, then some means is required to authenticate the identity of the sender.
Authentication of a message is often performed by the sender attaching an authentication `token` to the message. In the case of DES encipherment, this token may be referred to as the "Message Authentication Code" or MAC. The sender generates an authentication token from the text of the message using a secret key known only to the sender and receiver. The sender then transmits the token, along with the message, to the receiver. When the message has been succesfully received, the receiver generates his own version of the token, from the text of the message, using the secret key, and compares it with the received token. If the two versions of the token are identical, the authenticity of the message has been established.
The use of authentication tokens provides assurance, to the receiver, of the authenticity of the sender's identity and the message content in all cases except that of a dispute between the sender and receiver themselves. For reasons described more fully below, it is possible for the sender to repudiate, or deny the initiation of, a message received by the receiver, on the grounds that the receiver could have enciphered the message and generated the corresponding token himself. In other words, because it is within the ability of the receiver to forge a message and corresponding token, the receiver cannot prove that a received message and token originated at the sender. This problem illustrates the need for a non-repudiation technique which can provide further evidence of the origin of a message. Such a technique would increase confidence in the use of electronic networks such as automated electronic value transfer systems.
In particular, symmetric authentication algorithms have the obvious weakness that the same key is known to both sender and receiver, and in fact the authentication token is generated by the receiver during the authentication process.
In the case of asymmetric authentication algorithms, where the authentication token is usually referred to as the "digital signature" (DSG), it has been argued that because the sender and receiver hold different, complementary, keys, the receiver is able to verify but not to generate the sender's authentication token. The argument continues that if the token is valid, then the sender must have been responsible for the message. However, in order to maintain this argument as support for a claim of non-repudiation it must be shown that the key value used by the sender to generate the authentication token is held uniquely by the sender.
Asymmetric properties can also be achieved in symmetric encryption systems through the use of hardware controls which prevent a receiver from using his key to emulate the legitimate actions of the sender. The IBM 4753, 4754, and 4755 products have just such a property. (IBM is a registered trademark of the International Business Machines Corporation).
Several other approaches have been made to increase confidence in the authenticity of a message. U.S. Pat. No. 4,264,782 and U.S. Pat. No. 4,326,098, assigned to the assignee of the present invention, describe a security verification unit referred to as a "vault," the purpose of which is to act as a secure repository of the encryption keys corresponding to a number of associated data terminals. These keys are used to establish the authenticity of communications between terminals.
U.S. Pat. No. 4,393,269, assigned to the assignee of the present invention, relates to protocols whereby the recipient of a message is able locally to establish, with differing levels of confidence, the integrity of a received message.
All of the systems described above base the integrity of the sender's identity and the message content on the assumed fact that the sender's key is unique. In both the symmetric and the asymmetric approaches, the secret keys are protected through the use of hardware designed to be resistant to tampering, or physical or electronic attack. The property of key uniqueness is thus predicated upon the trustworthiness of the hardware itself and the security procedures used to manage the hardware. The assumed uniqueness of the sender's key may therefore be compromised for one of several reasons:
a) By pure chance; this is unlikely but impossible to disprove;
b) By legitimate intent; to facilitate backup or capacity requirements, several identical hardware units may need to exist;
c) By illegitimate intent; where legitimate intent is made possible within an organization by working practices within that organization, then such practices may be subverted by blackmail or threat;
d) By accident; it is imperative that key management authorities do not assign the same keys and identities to two or more data processing units, and do not initialize a unit whose hardware is not shown to be secure. However, either objective may be accidentally breached.
Irrespective of the cause of key duplication, there is always the possibility of its occurrence.
Further attacks on the non-repudiation claim may be made. For example, if a hashing algorithm linking parts of the message together (which does not require secret keys) is found to be weak, then alternative data messages may be successfully attached to genuine authentication tokens. Such an attack on a commonly used hashing function (the ISO Standard Hash 2 function) has been identified. This makes it difficult to show that the data belonged to its associated authentication token when the message was initiated.
The prior art does not provide, therefore, a strong technique for supporting a claim of non-repudiation of a message.